package kmp;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class leetCode678_checkValidString {

    public boolean checkValidString(String s) {
        Stack<Integer> leftq = new Stack<>();
        Stack<Integer> sunq = new Stack<>();
        for (int i = 0; i < s.toCharArray().length; i++) {
            char c = s.charAt(i);
            if(c == '('){
                leftq.push(i);
            } else if(c == '*'){
                sunq.push(i);
            }else{
                if(!leftq.isEmpty()){
                    leftq.pop();
                } else if(!sunq.isEmpty()){
                    sunq.pop();
                }else{
                    return false;
                }
            }
        }
        while (!leftq.isEmpty() && !sunq.isEmpty()){
            int leftIndex = leftq.pop();
            int sumIndex = sunq.pop();
            if(leftIndex > sumIndex){
                return false;
            }
        }
        return leftq.isEmpty();


    }



}
